namespace Bell {
	const int N = 55;
	const int MOD = 1000000007;
	int C[N][N], B[N];
	int pow_mod(int x, int k);
	void init() {
		for (int i = 0; i < N; i++) {
			C[i][0] = C[i][i] = 1;
			for (int j = 1; j < i; j++)
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
		B[0] = 1;
		for (int i = 1; i < N; i++) {
			B[i] = 0;
			for (int j = 0; j < i; j++) 
				B[i] = (B[i] - 1LL * C[i + 1][j] * B[j] % MOD + MOD) % MOD;
			B[i] = 1LL * B[i] * pow_mod(C[i + 1][i], MOD - 2) % MOD;
		}
	}
	//0^k + 1^k + ... + (n - 1)^k
	int cal(int n, int k) {
		int ans = pow_mod(k + 1, MOD - 2), sum = 0;
		for (int i = 0; i <= k; i++)
			sum = (sum + 1LL * C[k + 1][i] * B[i] % MOD * pow_mod(n, k + 1 - i) % MOD) % MOD;
		return 1LL * ans * sum % MOD;
	}
}
